Computer-aided techniques are known to include Computer-Aided Design or CAD, which relates to software solutions for authoring product design. Similarly, CAE is an acronym for Computer-Aided Engineering, e.g. it relates to software solutions for simulating the physical behavior of a future product. CAM stands for Computer-Aided Manufacturing and typically includes software solutions for defining manufacturing processes and operations.
A number of systems and programs are offered on the market for the design of objects (or parts) or assemblies of objects, forming a product, such as the one provided by Dassault Systemes under the trademark CATIA. These CAD systems allow a user to construct and manipulate complex three dimensional (3D) models of objects or assemblies of objects. CAD systems thus provide a representation of modeled objects using edges or lines, in certain cases with faces. Lines or edges may be represented in various manners, e.g. non-uniform rational B-splines (NURBS). These CAD systems manage parts or assemblies of parts as modeled objects, which are mostly specifications of geometry. Specifically, CAD files contain specifications, from which geometry is generated, which in turn allow for a representation to be generated. Geometry and representation may be stored in a single CAD file or multiple ones. CAD systems include graphic tools for representing the modeled objects to the designers; these tools are dedicated to the display of complex objects—the typical size of a file representing an object in a CAD system being in the range of one Megabyte per part, and an assembly typically comprising thousands of parts. A CAD system manages models of objects, which are stored in electronic files.
Also known are Product Lifecycle Management (PLM) solutions, which refer to a business strategy that helps companies to share product data, apply common processes, and leverage corporate knowledge for the development of products from conception to the end of their life, across the concept of extended enterprise. By including the actors (company departments, business partners, suppliers, Original Equipment Manufacturers (OEM), and customers), PLM may allow this network to operate as a single entity to conceptualize, design, build, and support products and processes.
Some PLM solutions make it for instance possible to design and develop products by creating digital mockups (a 3D graphical model of a product). The digital product may be first defined and simulated using an appropriate application. Then, the lean digital manufacturing processes may be defined and modeled.
The PLM solutions provided by Dassault Systemes (under the trademarks CATIA, ENOVIA and DELMIA) provides an Engineering Hub, which organizes product engineering knowledge, a Manufacturing Hub, which manages manufacturing engineering knowledge, and an Enterprise Hub which enables enterprise integrations and connections into both the Engineering and Manufacturing Hubs. All together the system delivers an open object model linking products, processes, resources to enable dynamic, knowledge-based product creation and decision support that drives optimized product definition, manufacturing preparation, production and service.
Such PLM solutions comprise a relational database of products. The database comprises a set of textual data and relations between the data. Data typically include technical data related to the products said data being ordered in a hierarchy of data and are indexed to be searchable. The data are representative of the modeled objects, which are often modeled products and processes.
Product lifecycle information, including product configuration, process knowledge and resources information are typically intended to be edited in a collaborative way. This is known as the field of collaborative design of virtual complex product. “Collaborative design” means that at least two users modify concurrently a common product. “Virtual complex product” means that the product being designed is modeled by an abstract data structure stored in a computer memory and that this data structure includes typed objects linked by typed relationships.
Industrial collaborative design is two folded: “instant collaboration” and “concurrent engineering”. On one hand, instant collaborative design is for designers within a small team (approximately two to ten people) to collaborate about a new product. They work in a “brainstorm” mood and each member of the team has to exchange, integrate and modify rapidly new ideas sent by other designers. On the other hand, concurrent engineering involves hundreds of designers working on a complex product through a well defined process. This process manages data ownership, data read and write access. The product is partitioned in such a way that designers can only modify a predefined subset of the whole product, on which they have read and write access. For this purpose, the boundary interface of each designer's working domain is clearly identified so that interaction with other designs is under control.
Academic research addresses the problem of merging two graphs (also called “views” or “models” or “schemas”) given the fact that they possibly share a common sub-graph. These graphs are an abstract and partial translation of an application world. The problem is easily solved by the push-out operation of category theory. Rewriting rules are modeled by “single push-outs” or “partial morphisms”. They are used a priori to define operations on graphs preserving the application semantic.
The article entitled “On the use of graph transformation for model refactoring” by T. Mens, of the University of Mons-Hainaut, in Belgium, relates to model refactoring, and shows how graph transformation can provide formal support for this activity. The article entitled “Scenario integration via higher-order graphs”, in Technical report No. 2006-517, by Z. Diskin, J. Dingel, H. Liang, from Queen's University, in Kingston, Ontario, Canada, 2006, also presents the use of graph theory for the management of scenarios involving models.
The thesis entitled “A relation-algebraic approach to graph structure transformation”, by W. Kahl, from University of Munich, in Germany, 2002, includes a statement about “the categoric approach to graph transformation”. It explains basic categorical push-out and pull-back operations as well as the “double push-out” graph rewriting.
The article entitled “Finding maximal cliques: new insight into an old problem” by F. Cazals, C. Karande, in INRIA research report No 5615, France, January 2007, provides a complete bibliography of the “maximal clique enumeration algorithm”. This algorithm is useful to provide conflict free partial solutions.
Some prior art relates to merging two graphs sharing a common sub-graph. This approach fails to identify elements concurrently modified by two users. The fact that an element a of the initial graph is replaced by an element b in a first modified graph and by an element b′ in a second modified graph is not captured. There is no place for this information because element a is not shared by modified graphs. Consequently, a conflict of this kind is out of reach. Furthermore, using single push-out rewriting rules or partial morphism rewriting rules fails to identify the invariant part of the rewriting process, which allows conflict checking. Obviously, this is a consequence of the restricted model (two graphs sharing a common sub-graph) since concurrently overwritten elements are totally missed.
Despite they can freely exchange information, instant collaborative designers have to merge by hand the features sent by other team members. One prior art application is based on declarative solid modeling and deals with mechanical part design.
Concurrent engineering designers own a predefined subset of the product. They may not modify the product elsewhere. When a distant change is necessary, a local try is possible (by duplicating distant data into the working domain), but the actual change is made by the data owner. Consequently, a heavy “conflict solving” process is required through mails, calls or even negotiation meetings so that the design change is well understood.
Thus, there still exists a need for an improved way of merging a first modeled object with a second modeled object.